/************************************************************************
Copyright (c) 2010, 2013, C.R. All rights reserved. 

E-mail: crtoyou@gmail.com; crtoyou@163.com

You can redistribute it and/or modify it under the terms of the
GNU Lesser General Public License as published by the
Free Software Foundation version 3 of the License.

This source code is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program. if not, write to the Free Software Foundation, Inc., 
51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA
************************************************************************/

#ifndef __CR_BITS_PLUS_IN_MORE_BYTES_H__
#define __CR_BITS_PLUS_IN_MORE_BYTES_H__

#include <crbitio.h>

/* use 32 bit mode */
#ifndef MSK_DEF
#define MSK_UNIT_TYPE            uint32
#define MSK_UNIT_BITS            (8*sizeof(uint32))
#define MSK_ALLOC_BITS(MSK)      (8*sizeof(MSK))
#define MSK_DEF(MSK, SIZ)       MSK_UNIT_TYPE MSK[(SIZ)/(MSK_UNIT_BITS)+1]
#define MSK_CHK_POS(SIZ, POS)   ((POS)>=0&&(POS)<(SIZ))
#define MSK_PB_(POS)             ((MSK_UNIT_TYPE)(POS)/(MSK_UNIT_BITS))
#define MSK_Pb_(POS)             (0x1<<((MSK_UNIT_TYPE)(POS)%(MSK_UNIT_BITS)))
#define MSK_SET_BIT(MSK, POS)    (MSK[MSK_PB_(POS)]|=MSK_Pb_(POS))
#define MSK_CLR_BIT(MSK, POS)    (MSK[MSK_PB_(POS)]&=~MSK_Pb_(POS))
#define MSK_FIL_BIT(MSK, POS, F) ((F)?(MSK_SET_BIT((MSK),(POS))):(MSK_CLR_BIT((MSK),(POS))))
#define MSK_CHK_BIT(MSK, POS)    (!!(MSK[MSK_PB_(POS)]&MSK_Pb_(POS)))
#endif

namespace cr {

template <typename T, typename argT = T>
struct bitbase
{
	T oBy;
	char obi;

	operator bitbase<argT> ()
	{
		return bitbase<argT>(oBy, obi);
	}

	explicit bitbase(T By = 0, char bi = 0)
	{
		oBy = By;
		obi = bi;
	}

	bitbase(const bitbase& other)
		: oBy(other.oBy), obi(other.obi)
	{}

	bitbase& operator = (const bitbase& other)
	{
		oBy = other.oBy;
		obi = other.obi;
		return *this;
	}

	bitbase& operator += (size_t len)
	{
		len += obi;
		oBy += len >> 3;
		obi = len & 7;
		return *this;
	}

	friend bool operator == (bitbase op1, bitbase op2)
	{
		return op1.oBy == op2.oBy && op1.obi == op2.obi;
	}

	friend bool operator != (bitbase op1, bitbase op2)
	{
		return !(op1 == op2);
	}

	friend bool operator < (bitbase op1, bitbase op2)
	{
		return op1.oBy < op2.oBy || (op1.oBy == op2.oBy && op1.obi < op2.obi);
	}

	friend bool operator >= (bitbase op1, bitbase op2)
	{
		return !(op1 < op2);
	}

	friend bool operator > (bitbase op1, bitbase op2)
	{
		return op1.oBy > op2.oBy || (op1.oBy == op2.oBy && op1.obi > op2.obi);
	}

	friend bool operator <= (bitbase op1, bitbase op2)
	{
		return !(op1 > op2);
	}
};

typedef bitbase<size_t> bit_size;
typedef bitbase<byte*, const byte*> bit_addr;
typedef bitbase<const byte*> const_bit_addr;

template <uint16 SIZ_BITS>
class bitvector 
{
protected:
	class bitref
	{
	private:
		bitref& operator = (const bitref& other);
	protected:
		bitvector &refunit_;
		const uint16 refpos_;
	public:
		bitref(const bitvector& refunit, uint16 refpos)
			: refunit_(*const_cast<bitvector*>(&refunit)), refpos_(refpos) {}
		__forceinline bitref& operator = (bool bi)
		{	refunit_.filbit(refpos_, bi); return *this; }
		__forceinline operator bool() const
		{	return refunit_.chkbit(refpos_); }
	};
public:
	__forceinline bitref operator[](uint16 i) { return bitref(*this, i); }
	__forceinline const bitref operator[](uint16 i) const { return bitref(*this, i); }

public:
	bitvector(bool bInitVal = false)
	{
		::memset(bits_, (bInitVal ? 0xFF : 0), sizeof(bits_));
	}

	bitvector(const bit_addr buf)
	{
		::bitcpy(bits_, buf.oBy, SIZ_BITS, 0, buf.obi);
	}

	bitvector(const bitvector& other)
	{
		memcpy(bits_, other.bits_, sizeof(bits_)); 
	}

	bitvector& operator=(const bitvector& other)
	{
		memcpy(bits_, other.bits_, sizeof(bits_));
		return *this;
	}

	inline void negall()
	{
		for (int i=0; i<_countof(bits_); ++i) {
			((MSK_UNIT_TYPE*)bits_)[i] =~ ((MSK_UNIT_TYPE*)bits_)[i];
		}
	}

	inline void setbit(uint16 i_pos)
	{
		MSK_SET_BIT(bits_, i_pos); 
	}

	inline void clrbit(uint16 i_pos)
	{
		MSK_CLR_BIT(bits_, i_pos);
	}

	inline void filbit(uint16 i_pos, bool b)
	{
		MSK_FIL_BIT(bits_, i_pos, b); 
	}

	inline bool chkbit(uint16 i_pos) const
	{
		return MSK_CHK_BIT(bits_, i_pos);
	}

protected:
	MSK_DEF(bits_, SIZ_BITS);

};

//child mask of parent mask except the bit i_pos. 
//generally used in matrix maths, to define the submatrix. 
template <uint16 SIZ_BITS>
class bitmask : public bitvector<SIZ_BITS>
{
public:
	bitmask(bool bInitVal = false) : bitvector(bInitVal)
	{}

	bitmask(const bit_addr buf)
		: bitvector(buf)
	{}

	bitmask(const bitmask& other)
		: bitvector(other)
	{}

	bitmask(const bitmask& parent, uint16 clr_i)
		: bitvector(parent)
	{
		__super::clrbit(seek(clr_i));
	}

	inline bitmask& operator = (const bitvector& other)
	{
		memcpy(bits_, other.bits_, sizeof(bits_));
		return *this;
	}

	//i_index seeks in valid bits_. 
	//i_pos seeks the bit position where the i_index seek. 
	inline uint16 seek(uint16 i_index) const
	{
		return ::bitfind(bits_, SIZ_BITS, i_index, 0);
	}

	//disable these functions
	//and don't use the macros which are same as these. 
private:
	inline void setbit(uint16 i_pos);
	inline void clrbit(uint16 i_pos);
	inline void filbit(uint16 i_pos, bool b);
	inline bool chkbit(uint16 i_pos) const;
};


template <uint16 SIZ_BITS>
class bitstring : public bitvector<SIZ_BITS>
{
public:
	bitstring() 
		: bitlen_(0)
	{}

	bitstring(const bit_addr buf, uint16 len)
		: bitvector(buf)
		, bitlen_(len)
	{}

	template <uint16 SIZ_BITS_OTHER>
	inline bitstring& operator = (bitstring<SIZ_BITS_OTHER> other)
	{
		ASSERT(other.length() <= SIZ_BITS);
		setbits(other.begin(), other.length());
		return *this;
	}

	inline const_bit_addr begin() const
	{
		return const_bit_addr(buffer(), 0);
	}

	inline const_bit_addr end() const
	{
		return begin() += length();
	}

	inline const byte* buffer() const 
	{
		return (byte*)bits_;
	}

	inline uint16 length() const
	{
		ASSERT(bitlen_ <= SIZ_BITS);
		return bitlen_;
	}

	inline void setbits(const_bit_addr buf, uint16 len)
	{
		ASSERT(len > 0);
		::bitcopy((byte*)bits_, buf.oBy, len, 0, buf.obi);
		bitlen_ =len;
	}

	inline void catbits(const_bit_addr buf, uint16 len)
	{
		ASSERT(len > 0);
		ASSERT(bitlen_ < SIZ_BITS);
		ASSERT(bitlen_ + len <= SIZ_BITS);
		bit_addr pos((byte*)bits_, 0);
		pos += bitlen_;
		::bitcopy(pos.oBy, buf.oBy, len, pos.obi, buf.obi);
		bitlen_ += len;
	}

	inline void append(bool bi)
	{
		ASSERT(bitlen_ < SIZ_BITS);
		filbit(bitlen_++, bi);
	}

	inline void insert(bool bi, uint16 pos = (uint16)-1)
	{
		ASSERT(bitlen_ < SIZ_BITS);
		if (pos >= bitlen_) {
			filbit(bitlen_++, bi);
		}
		else {
			uint16 i = bitlen_;
			while (--i >= pos)
				filbit(i+1, chkbit(i));
			filbit(pos, bi);
			++bitlen_;
		}
	}

	inline void insert(const_bit_addr buf, uint16 len, uint16 pos = (uint16)-1)
	{
		ASSERT(len > 0);
		ASSERT(bitlen_ < SIZ_BITS);
		ASSERT(bitlen_ + len <= SIZ_BITS);
		if (pos >= bitlen_) {
			bitcat(buf.oBy, len, buf.obi);
		}
		else {
			uint16 i = bitlen_;
			while (--i >= pos)
				filbit(i+len, chkbit(i));
			uint16 from = buf.obi;
			for (i=0; i<len; ++i)
				filbit(pos++, MSK_CHK_BIT(buf.oBy, from++));
			bitlen_ += len;
		}
	}

	inline void erase(uint16 pos = (uint16)-1, uint16 len = 1)
	{
		ASSERT(len > 0);
		ASSERT(bitlen_ <= SIZ_BITS);
		ASSERT(len <= bitlen_);
		if (pos == (uint16)-1) {
			bitlen_ -= len;
		}
		else if (pos > 0 && pos < bitlen_) {
			uint16 tail = pos + len;
			while (tail < bitlen_)
				filbit(pos++, chkbit(tail++));
			bitlen_ = pos;
		}
		else {
			// pos beyond end, ignore
		}
	}

	inline void clear()
	{
		bitlen_ = 0;
	}

	inline int findtrue(uint16 ifrom = 0) const 
	{
		ASSERT(bitlen_ <= SIZ_BITS);
		if (bitlen_ <= 0)
			return -1;
		return bitseek(bits_, bitlen_, 0, ifrom);
	}

	inline int findfalse(uint16 ifrom = 0) const
	{
		ASSERT(bitlen_ <= SIZ_BITS);
		if (bitlen_ <= 0)
			return (uint16)-1;
		bitstring tmp(*this);
		tmp.negall();
		return tmp.findtrue(ifrom);
	}

	inline bitstring& operator += (const bitstring& other)
	{
		if (other.length() > 0)
			catbits(other.begin(), other.length());
		return *this;
	}

	inline friend bitstring operator + (const bitstring& bs1, const bitstring& bs2)
	{
		bitstring bs = bs1;
		if (bs2.length() > 0)
			bs.catbits(bs2.begin(), bs2.length());
		return bs;
	}

protected:
	uint16 bitlen_;

#ifdef _DEBUG
public:
	inline size_t dump(bool vals[], size_t bufsize) const
	{
		ASSERT(bufsize >= bitlen_);
		if (bitlen_ > 0)
			::bitread(vals, bits_, bitlen_);
		return bitlen_;
	}
	inline void dump() const 
	{
		bool vals[256];
		dump(vals, 256);
		for (int i=0; i<bitlen_; ++i) {
			TRACE(_T("%c"), vals[i]?_T('1'):_T('0'));
		}
	}
#endif 

};

}//namespace

#endif//__CR_BITS_PLUS_IN_MORE_BYTES_H__